The present invention relates to an information processing device and method thereof, and a transmission medium, and more particularly relates to an information processing device and method thereof and a transmission medium by which an amount of information for an object to be processed is reduced in such a manner that processing can be carried out at high speed.
With information processing devices such as computer games, various three-dimensional figures (objects) are represented, with the objects being possible to be changed in various states. FIG. 1 is a block diagram showing an example of a configuration of such kind of information processing device. In this example, a CPU 11 carries out various calculations such as coordinate transformations, light source calculations or vector arithmetics etc., as well as controlling of each part. Further, to the CPU 11, there are connected a main bus 12 that carries out data transfer at a comparatively high speed and a sub-bus 13 that carries out the data transfer at a comparatively low speed, via which data can be exchanged. A CD-ROM drive 14 is connected to the sub-bus 13 so that various data or programs can be read out from a CD-ROM as a recording media installed in the CD-ROM drive 14 using instructions of the CPU 11.
A main memory 15 and a GPU (Graphics Processing Unit) 16 are connected to the main bus 12. The main memory 15 stores data such as data read our from the CD-ROM driver 14 and data as computation results of the CPU 11. The GPU 16 reads out data from the main memory 15 as required, carries out rendering processing, and stores the processed data in a VRAM (Video Random Access Memory) 17 as pixel data. The GPU 16 further reads out pixel data stored in the VRAM 17 and supplies this data to a D/A converter 18. The D/A converter 18 converts the pixel data supplied from the GPU 16 from a digital signal to an analog signal for being outputted to a monitor (not shown) as a video signal.
With this kind of information processing device, a prescribed object is represented with triangular polygons as the units. One triangle is composed of three vertexes, and coordinate data for these three vertexes is therefore required as data representing this triangle. For example, as shown in FIG. 2, when a ribbon-shaped object 21 is formed from triangles 22-1 to 22-8 (in this drawing, each triangle is shown separately to make the description easier), if the data for each triangle is taken to be expressed as {Pa, Pb, Pc}, the data for this object 21 can be expressed as Triangle {P0, P1, P2}+Triangle {P1, P2, P3}+Triangle {P2, P3, P4}+Triangle {P3, P4, P5}+Triangle {P4, P5, P6}+Triangle {P5, P6, P7}+Triangle {P6, P7, P8}+Triangle {P7, P8, P9}.
The number of items of data required to define an object formed using N triangles is therefore 3N.
On the other hand, as shown in FIG. 3, after, for example, the first triangle 22-1 is formed using vertexes P0, P1 and P2, the next triangle 22-2 can be formed if the vertex P3 is specified. The triangles for the following stages can then be expressed in a similar manner by sequentially specifying the vertexes P4 to P9 one at a time. This is to say that, with the exception of the first triangle 22-1, one triangle can be expressed using one vertex. Such a data format by which a figure (object 21) where triangles are linked in a ribbon shape is expressed as a series of successive points is referred to as a xe2x80x9cTriangle Stripxe2x80x9d (hereinafter abbreviated to xe2x80x9cstripxe2x80x9d according to situations). Data for an object 21 as a strip can then be expressed as a Triangle Strip {P0, P1, P2, P3, P4, P5, P6, P7, P8, P9}.
When an object 21 is defined using a series of successive points in this way, the number of items of required data is 3+(Nxe2x88x921)=N+2, and the amount of data (information) can be reduced compared with that in the case shown in FIG. 2.
Further, as shown in FIG. 4, a fan-shaped object 31 can be formed by making vertexes P1 to P5 correspond to vertex P0. In this case, one triangle can also be represented by one vertex as, Triangle Fan {P0, P1, P2, P3, P4, P5}. This kind of data format is referred to as a triangle fan (Triangle Fan) (hereinafter abbreviated to xe2x80x9cfanxe2x80x9d according to situations).
Incidentally, a single triangle can be drawn using data for coordinates for three vertexes, three vertex colors and three normal vectors. A description will now be given with reference to FIG. 5 of, for example, the process for drawing the object 21 shown in FIG. 3 with individual triangles taken as the units. First, in step S101, the CPU 11 reads out three-dimensional coordinate data, color data and a normal vector corresponding to a prescribed vertex of the three vertexes of one triangle from the main memory 15. In step S102, the read out three-dimensional coordinate data is transformed to coordinates in a virtual space.
In step S103, the CPU 11 carries out perspective transformation of the three-dimensional coordinate data that has been converted in step S102 into two-dimensional coordinate data. Namely, the three-dimensional coordinates of the triangle put in the virtual space are converted to coordinates for a state viewed in two dimensions (a state viewed on a monitor). Following this, in step S104, the CPU outputs the two-dimensional coordinate data obtained in step S103 to the GPU 16.
In step S105, the CPU 11 calculates the luminance at each vertex from the position and direction of a light source in virtual space, with color data corresponding to the calculation results of step S105 being outputted to the GPU 16 in step S106.
In step S107, a determination is made as to whether or not processing for all (three) of the vertexes for one triangle is complete. When it is determined that there still exist vertexes that have not yet been processed, the process returns to step S101 and processing for the next vertex is carried out. When it is determined in step S107 that processing is complete for all of the vertexes, the process proceeds to step S108 to go to processing of the GPU 16.
In step S108, the GPU 16 draws the triangle formed by three vertexes through Gouraud shading with the data corresponding to the three vertexes supplied by the CPU 11. In step S109, a determination is made as to whether or not drawing for all of the triangles is complete (whether or not drawing of the object 21 is completed). When it is determined that there still exist triangles that have not yet been drawn (drawing of the object 21 is not completed), the process returns to step S101 and the same processing is carried out on other triangles of FIG. 3.
When it is determined in step S109 that drawing is complete for all of the triangles (drawing of the object 21 is complete), the processing is complete.
The processing occurring at the GPU 16 in step S108 will now be further described. For example, if normal vectors 51-1 to 51-3 at each vertex A, B and C of a triangle 61 to be processed are taken to be directed in directions shown in FIG. 6, a normal vector 51-4 at the center point D of the triangle 61 is interpolated by the GPU 16 from these normal vectors. The triangle 61 therefore has a bulge toward a central part. Therefore, when light giving illumination from a light source 41 is considered, as shown in FIG. 7, Gouraud shading has to be carried out in such a manner that the triangle 61 is brighter in the center part thereof and becomes darker toward the edges.
Gouraud shading, however, is processing that only interpolates color. Therefore, for example, when each vertex is given with the same color, the triangle 61 becomes completely painted out as shown in FIG. 8, and its accurate shape cannot be shown as a three-dimensional body. Processing for drawing is therefore carried out by finely subdividing the triangle 61 as shown in a flowchart of FIG. 8.
First, in step S121, the CPU 11 reads from the main memory 15 data for the triangle 61, which is then finely subdivided into a prescribed number (in this case, 16) of triangles (hereinafter referred to as sub-triangles for discrimination) as shown in FIG. 10A. In step S122, normal vectors for vertexes of newly generated sub-triangles are interpolated using normal vectors 51-1 to 51-3. Data for each vertex and normal vector thereof is then made to be temporarily stored in the main memory 15.
Next, processing of step S123 to step S130 is carried out but description thereof is omitted because this processing corresponds to that of step S101 to step S108 of FIG. 5. When the processing for step S123 to step S130 is complete, the process proceeds to step S131 and a determination is made as to whether or not drawing of all of the sub-triangles is complete. When it is determined that sub-triangles that have not been drawn still exist, the process returns to step S123 to go to processing for the next sub-triangle.
When it is determined in step S131 that processing for drawing all of the sub-triangles is complete, the processing comes to an end. The triangle 61 can therefore be expressed in more detail, as shown in FIG. 10B.
FIG. 11 shows an example of this method applied to a strip 71. In this example, triangles 81-1 to 81-8 forming the strip 71 are individually and finely subdivided into finer sub-triangles. In this case, each triangle (for example, 81-1) is divided into a total of 16 sub-triangles. This triangle 81-1 is then defined by sub-strips (sub-triangle strips) 91-1 to 91-4 with the number of the sub-triangles being 1, 3, 5 and 7, respectively, i.e. with the number of vertexes being 3, 5, 7 and 9, respectively, as shown in FIG. 12.
When a length N of the strip 71 of the series of vertexes of P0 to P9 is then defined as 10, the number of triangles comprising this strip 71 is Nxe2x88x922=8. Eight of sub-strips are therefore generated for each of lengths 3, 5, 7 and 9 after dividing. Because of this, if processing time for drawing on sub-triangle is taken to be T0 and time required for initialization setting of one sub-strip is taken to be T1, processing time T for drawing one strip becomes as follows. The processing time T0 changes depending on the area and shape of the triangle to be processed, but for convenience of the description, that processing time is assumed to be the same.                                                         T              =                              xe2x80x83                            ⁢                              {                                                      (                                          T1                      +                                              T0                        xc3x97                        1                                                              )                                    +                                      (                                          T1                      +                                              T0                        xc3x97                        3                                                              )                                    +                                      (                                          T1                      +                                              T0                        xc3x97                        5                                                              )                                    +                                                                                                                                          xe2x80x83                                ⁢                                  (                                      T1                    +                                          T0                      xc3x97                      7                                                        )                                }                            xc3x97                              (                                  N                  -                  2                                )                                                                                        =                              xe2x80x83                            ⁢                                                (                                                            4                      xc3x97                      T1                                        +                                          16                      xc3x97                      T0                                                        )                                xc3x97                                  (                                      N                    -                    2                                    )                                                                                                        =                              xe2x80x83                            ⁢                                                T1                  xc3x97                  4                  ⁢                                      (                                          N                      -                      2                                        )                                                  +                                  T0                  xc3x97                                      (                                                                  16                        ⁢                        N                                            -                      32                                        )                                                                                                          (        1        )            
In this case, the number of vertexes possessed by a single triangle is 15. Therefore, when data for a strip of length N is stored, it is necessary to store information for all of the vertexes and the memory capacity required becomes 15xc3x97(Nxe2x88x922).
Similarly, as shown in FIG. 13, when a fan 101 of length N (=6) is finely subdivided, each of the triangles 111-1 to 111-4 forming the fan 101 is subdivided into sub-strips of lengths 3, 5, 7 and 9, with the number of Nxe2x88x922 (=4) for each. The processing time T for the triangle fan after fine subdividing can therefore also be given by equation (1).
Fine subdividing can therefore be carried out for a prescribed object.
However, the amount of information for the object after fine subdividing becomes large and processing time becomes long accordingly.
In view of the above, the present invention sets out to reduce the amount of information for an object to be processed and carry out processing at high-speed.
An object of the invention is to provide an information processing device wherein a plurality of first points defining first information are interpolated in such a manner as to generate second points and a plurality of pieces of second information defined by a plurality of the second points are generated, comprising:
interpolating means for interpolating the second points from the first points; and
generating means for generating the second information by combining the second points interpolated by the interpolating means in a direction of length of the first information.
Another object of the invention is to provide an information processing method for an information processing device wherein a plurality of first points defining first information are interpolated in such a manner as to generate second points and a plurality of pieces of second information defined by a plurality of the second points are generated, comprising:
an interpolating step of interpolating the second points from the first points; and
a generating step of generating the second information by combining the second points interpolated in the interpolating step in a direction of length of the first information.
A further object of the invention is to provide a transmission medium for transmitting a program employed by an information processing device wherein a plurality of first points defining first information are interpolated in such a manner as to generate second points and a plurality of pieces of second information defined by a plurality of the second points are generated, characterized by transmitting a program comprising:
an interpolating step of interpolating the second points from the first points; and
a generating step of generating the second information by combining the second points interpolated in the interpolating step in a direction of length of the first information.
In the information processing device, the information processing method, and the transmission medium according to this invention, the second points are interpolated from the first points, to generate the second information by combining the second points in the direction of the length of the first information.